#include <iostream>
#include <vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
    unordered_map<string, vector<char>> mp;
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        for (string str : allowed) {
            mp[str.substr(0, 2)].push_back(str.back());
        }
        string upper = "";
        return gogogo(bottom, upper, 0);
    }

    bool gogogo(string bottom, string upper, int pos) {
        if (pos == bottom.size() - 1) {
            if (upper.size() == 1) return true;
            bottom = upper;
            upper = "";
            pos = 0;
        }
        vector<char>& vc = mp[bottom.substr(pos, 2)];
        if (vc.empty()) return false;
        else {
            for (int i = 0; i < vc.size(); i++) {
                if (gogogo(bottom, upper + vc[i], pos + 1)) return true;
            }
        }
        return false;
    }
};
int main()
{
	return 0;
}